The invention generally relates to error-correction coding or more particularly, the invention relates to history handling for Viterbi decoding.
Viterbi decoding of convolutionally encoded messages is a common error-control method in the field of digital communications systems, and is well known in the art as described in U.S. Pat. No. 5,742,621, and Motorola Application Report APR40/D, revision 0, May 1998. Software based Viterbi decodes are commonly used in digital communication systems due to the availability of low cost, high performance digital signal processors (DSPs). In conventional software implementations the handling of the history, associated with the decoding path, amounts to a substantial potential of the Viterbi decoder processing time. It is common in the art to have a collection of history bits associated with each state, and a comparison/selection operation, which includes the setting of history bit, for each state, as a method of handling the history.
FIG. 1 depicts a common rate xc2xd, constraint length K=7, binary convolutional encoder, using a shift register with Kxe2x88x921=6 memory elements. This encoder has N=2Kxe2x88x921=26=64 states. For every input data bit, d(i) two coded bits, c1(i) and c2(i), are generated. The encoder is a state machine whose state is [d(ixe2x88x92(kxe2x88x922)), . . . , d(ixe2x88x921), d(i)] at time i, and has generator polynomials g1=[1011011]2 and g2=[1111001]2. The generator polynomials specify how delayed versions of the input are added up (modulo-2) to produce each output. Each binary digit (bit) of the generator polynomial corresponds to a tap on the shift register, or a tap on the input data bit. The output of the encoder is determined by the generator polynomials (as well as the state of the encoder and the input data bit), but the state transitions are independent of the polynomials, and depend only on the current state and the input data bit.
In the Viterbi algorithm (VA), both a state history Hn(i) and a state metric Mn(i) are associated with each state n, at time i. There is an associated branch metric Bnm(i) for each valid transition from state m to state n. In the particular example where K=7, states 0 (000000) and 32 (100000) can both go to either state 0 (000000) or state 1 (000001), depending on the input data bit. No other state transitions from states 0 and 32 are possible. The state metrics and the state histories are updated as follows:
Mn(f)=max/m[Mm(ixe2x88x921)+Bnm(i)]xe2x80x83xe2x80x83(1) 
Hn(i)=[Hn(ixe2x88x921), LSB(n)], m=best old state xe2x80x83xe2x80x83(2) 
These two equations referred to as the add-compare-select (ACS) operation, and the application of the add-compare select operation to all states at a given time is considered as one Viterbi advance.
The application of one Viterbi advance is represented in FIG. 3. In this case the memory of the convolutional encoder is 2, and hence there are 4 states. In conventional software VA implementations, two buffers are required. Each buffer must be capable of holding a full set of state metrics and histories: one for the previous, or xe2x80x9coldxe2x80x9d data, and one for the updated, or xe2x80x9cnewxe2x80x9d data. After new data is obtained the new data is used as the old data for a subsequent Viterbi advance.
In determining the new state history for a state, as in equation (2), the prior are method of history handling inserts the least significant bit of the state number of the new state into the state history. This is a critical aspect of prior art history handling, where a history bit has to be inserted each time a new history is generated.
History handling consumes a considerable portion of the processing resources in a typical Viterbi decoder implementation. There is, therefore, a need to reduce the complexity of the history handling to permit more practical and economical implementation of a Viterbi decoder.
An object of this invention is to provide an improved method of history handling for Viterbi decoders that reduces the processing time required to decode a convolutionally encoded message relative to conventional methods.
Therefore, in accordance with an aspect of the present invention, there is provided a method of processing the state histories within a Viterbi decoder, which receives a sequence of samples, representing a sequence of encoded data bits from a convolutional encoder having N states, and a memory size of Kxe2x88x921 bits, where Kxe2x89xa62, N=2Kxe2x88x921, and each state is uniquely identified by a sequence of Kxe2x88x921 state bits, which corresponds to Kxe2x88x921 data bits entered into the encoder. The method provided by the invention comprises the following steps. The first step is to define an initial state metric and an initial state history for each state. The second step is, for each state, insert, into the initial state history, L contiguous state bits that correspond to the L data bits first entered into the encoder, where 1xe2x89xa6Lxe2x89xa6Kxe2x88x921. The third step is to designate the initial state metrics and the initial state histories as previous state metrics and previous state histories respectively. The fourth step is to determine at least one branch metric, using no less than one of the samples received by the decoder. The fifth step in the process is to use the branch metric, or metrics, determined in the fourth step, to determine N new state metrics and N new state histories from the previous state metrics and the previous state histories, where each new state history is a copy of a previous state history. Upon reaching this point the decoding continues by repeating the fourth and fifth steps Lxe2x88x921 times, wherein the new state metrics and the new state histories become previous state metrics and the previous state histories, respectively, for subsequent repetitions of the fourth and fifth steps. Preferably L=Kxe2x88x921. In an embodiment of the invention, at least one bit of the state history is present in at least one bit of the least significant bits of a storage word storing the state metric.
In accordance with another aspect of the present invention there is provided a state history processor within a Viterbi decoder that receives and decodes a sequence of samples representing a sequence of encoded bits obtained from encoding a sequence of data bits with a convolutional encoder having N states and a memory size of Kxe2x88x921 bits, where Kxe2x89xa72, N=2Kxe2x88x921, and each state is uniquely identified by a sequence of Kxe2x88x921 state bits corresponding to Kxe2x88x921 data bits entered into the encoder, the previously mentioned processing being comprised of five elements. The first element is a set of N first buffers corresponding to the N states, where each first buffer is used for storing a previous history and a previous metric. The second element is a set of N second buffers corresponding to the N states, where each second buffer is used for storing a new history and a new metric. The third element is a means for determining an initial state metric and an initial state, for each state, that is to be stored in the corresponding second buffer. The fourth element is a means for inserting into each new history L contiguous state bits that correspond to L data bits first entered into the encoder, where L is at least one and at most Kxe2x88x921. The fifth element is a means for performing L advances, with each advance consisting of the following steps. Firstly, the first and second buffers"" designations are interchanged. Secondly, at least one branch metric is determined using at least one of the samples received by the decoder. Thirdly, N new state metrics and N new state histories are determined from the previous state metrics and the previous state histories, by using the at least one branch metric, wherein each new state history is a copy of one previous state history. Fourth, and finally, the N new state metrics and the N new state histories are stored in the N second buffers. An additional embodiment of this invention calls for a history processor, as previously described, wherein for each state at least one bit of the state history is present in at least one bit of the least significant bits of the state metric.
A significant advantage of this invention is the reduction in the computational complexity of the core of the Viterbi decoding algorithm. In the comparison of the present invention with the prior art approach of shifting each collection of history bits and then xe2x80x9cOR-ingxe2x80x9d in the new history bit, it becomes apparent that the present invention has a computational advantage. With the invention, there is no need either for the shift operation, or for the xe2x80x9cORxe2x80x9d operation. Additionally in order to choose the xe2x80x9cshift-and-ORxe2x80x9d approach to history bit handling, with embedded history, it would be necessary to ensure that the shifting did not affect the state metrics themselves. This concern is not present with this invention because the technique of embedding the history bits into the least significant bits of the state merits work well.
Another advantage of the present invention relates to its operation on processors with word-widths less than or equal to 16 bits, also referred to as narrow word-width processors. Such processors, using conventional history handling methods, cannot feasibly embed the history bits in the least significant bits of the metric storage words, except for the case of very short constraint-lengths. This inadequacy is demonstrated by a Kxe2x88x927 convolutional code (i.e. memory-6). With conventional history handling methods, the low 6 bits of history simply reproduce the state number. This means that at least 10 bits of each state metric storage word would have to be allocated for the history bits, since, for both computational and memory efficiency reasons, it is undesirable to store the history bits more often than every 4 bits processed. Thus, if 10 bits are reserved for history, only 6 bits remain for the state metrics themselves. Since the state metrics require several more bits of quantization than the input samples feeding the Viterbi decoder, the quantization of the input would be very coarse, Thus, for narrow word-width processors, using conventional history handling methods, the history bits have to be read, selected, updated, and written, independently of the same metrics. This substantially increases the processing requirements associated with the core of the Viterbi decoder. In one embodiment of the present invention, only 4 least-significant bits are needed to store the history bits, leaving 12 bits for the state metrics themselves. With the present invention, up to a xe2x80x9cmemoryxe2x80x9d history bits can be present at once, but there is no requirement to use this maximum number. In summary, for processors with word-widths less than or equal to 16 bits, the present invention allows the use of the xe2x80x9cembedded historyxe2x80x9d technique, which can result in a decoder throughput increase of approximately 50%.